1. Field of the Invention
The present invention relates to an apparatus and method for encoding an image. More particularly, it pertains to an apparatus and method for quantizing conversion data obtained by transforming image information to a frequency space so as to encode such data.
2. Related Background Art
An Adaptive Discrete Cosine Transformation (ADCT) encoding system used as a method for encoding color image signals has gained attention in recent years. A Joint Photographic Expert Group (JPEG), which was founded as an international organization for standardizing such an encoding system, will soon adapt the ADCT encoding system as an official encoding system.
The outline of such an encoding system will be described briefly.
FIG. 3 is a block diagram illustrating the approximate structure of a conventional encoding system utilizing DCT. FIGS. 4A to 4D are views illustrating the encoding system shown in FIG. 3. Numeral 2 denotes an input terminal of a digital image signal to be encoded. A raster scanned digital image signal is input from a CCD sensor (not shown) to the input terminal 2, and then to an 8.times.8 block formation circuit 4, where it is two dimensionally divided into 8.times.8 pixel blocks, and then transmitted pixel block by pixel block to components connected to the formation circuit 4.
Numeral 6 denotes a DCT converting circuit for changing the image signal transmitted from the block formation circuit 4 into discrete cosine transformation so as to output 8.times.8 data matrices regarding a frequency zone. In other words, the DCT converting circuit 6 converts pixel blocks forming image data items D.sub.11 to D.sub.88 shown in FIG. 4A into data matrices forming DCT coefficients X.sub.11 to X.sub.88 shown in FIG. 4B.
Data matrix coefficient X.sub.11 represents a DC component in horizontal and vertical directions of the pixel block, that is, the average value of the pixel block. When the DCT coefficients X.sub.11 to X.sub.88 are expressed as Xij, the greater the "i" increases, the higher the frequency a component has in the vertical direction; similarly, the greater the "j" increases, the higher the frequency the component has in the horizontal direction.
The data matrices output from the DCT converting circuit 6 are input to a linear quantization circuit 8. A quantization matrix generation circuit 18 generates quantization matrices W.sub.11 to W.sub.88 (shown in FIG. 4C) which show the weight of a step of quantizing the DCT coefficients X.sub.11 to X.sub.88. A coefficient generation circuit 16 generates coefficients C. The quantization matrices W.sub.11 to W.sub.88 and the coefficients C are input to a multiplier 20. The multiplier 20 calculates an equation (W.sub.ij .times.C/C.sub.0). A quantizing step performed by the linear quantization circuit 8 is determined in accordance with the outputs Q.sub.11 to Q.sub.88 of the multiplier 20. The coefficients C are positive values which control image quality and the amount of data generated, whereas C.sub.0 is a constant.
The linear quantization circuit 8 actually calculates an equation X.sub.ij /Q.sub.ij, and outputs it. The outputs of the linear quantization circuit 8 are expressed as quantized conversion data items G.sub.11 to G.sub.88. The quantized data items G.sub.11 to G.sub.88 are successively transmitted starting from DC components from a zigzag scan circuit 10. In other words, the data items G.sub.11 to G.sub.88 are supplied from the zigzag circuit 10 to a Variable Length Coding (VLC) circuit 12 in the order of G.sub.11, G.sub.12, G.sub.21, G.sub.31, G.sub.22, G.sub.13, G.sub.14, G.sub.23, G.sub.32, G.sub.41 . . G.sub.85, G.sub.86, G.sub.77, G.sub.68, G.sub.78 and G.sub.88.
As regards, for example, a DC component G.sub.11, the VLC circuit 12 calculates a predicted value between pixel blocks located near the DC component G.sub.11, and changes a difference between the predicted value and an actual value into a Huffman code. As regards AC components G.sub.12 to G.sub.88, since most of the coefficients appear to be zeros, group ID numbers, which identify groups into which significant coefficients except zero are divided according to the values of the significant coefficients, and values combined with the number of zeros preceded by the significant coefficients (run length of zeros) are formed into Huffman codes by the VLC circuit 12. Data indicating values in the groups, into which the significant coefficients are divided, is additionally coded.
In general, since the ratio at which high-frequency components occur in the diagonal direction of an image is low, it is predicted that, after zigzag scanning has been performed, in many cases all components become zero which occupy the latter half of the outputs represented by Gij and transmitted from the line quantization circuit 8. It is therefore expected that variable length codes thus obtained can be compressed at a very high ratio. If a compression ratio between 1 out of 2 and 1 out of 9 is employed, it is possible to reproduce an image having hardly deteriorated quality.
Generally, the amount of data transmitted through a transmission route per unit time is fixed. When one screen must be transmitted at each predetermined time interval, as when an image is transmitted, it is desirable that an output code be represented by a bit number fixed by an image or pixel block unit.
If a high value is given to the coefficients C mentioned previously, the ratio at which Gij assumes zero increases and the total number of bits of encoded data NB decreases. The relationship between the coefficients C and the total number of bits NB varies according to images, and is expressed by a monotonically decreasing function. It is known that such a relationship regarding an average image is expressed by the logarithmic curve shown in FIG. 4D.
The above-mentioned JPEG presents a method of predicting a coefficient C.sub.0 for obtaining the desired total number of bits NB0. A coefficient C.sub.1 is first encoded, and then the total number of bits nb1 of a thus-obtained code is determined. A predicted value C.sub.2 of the coefficient C.sub.0 is calculated on the basis of the total number of bits nb1. Such calculation can be predicted because the logarithmic curve shown in FIG. 4D runs through a point (C.sub.1, nb1).
By repeating the above operation several times, the amount of data encoded can be obtained within approximately several % errors with respect to the desired total number of bits NB0.
However, the process of repeatedly encoding data so as to determine the coefficients C is a very time-consuming process, and is not suitable for an encoding apparatus which is required to transmit one screen at predetermined time intervals, such as moving images. Such a process is extremely difficult to perform in terms of calculation speed, particularly when image signals of a very high bit rate, such as high definition television signals, are handled.